# 斐波那契
fib = lambda x: 1 if x in [1, 0] else fib(x-1) + fib(x-2)

def fb(n):
  return 1 if n in [0, 1] else fb(n-1) + fb(n-2)

# 阶乘
factorial = lambda x: 1 if x == 1 else x * factorial(x-1)

def factr(n):
  return 1 if n == 1 else n * factr(n-1)

# 不重复的最长子串
def findSubStr(dstr):
  tLst = list()
  tsub = list()
  for i in dstr:
    if i not in tLst:
      tLst.append(i)
    else:
      if len(tsub) < len(tLst):
        tsub = tLst[0:len(tLst)]
      idx = tLst.index(i)
      tLst.append(i)
      tLst = tLst[idx+1::]
  # 防止最后一个字符加入后的长度刚好超过前一个记录的子串长
  if len(tsub) < len(tLst):
    tsub = tLst
  return ''.join(tsub)


# 查找字符串中第一个不重复字符
def getone(dstr):
  if len(dstr) == 0:
    return None
  if len(dstr) == 1:
    return dstr
  tLst = list(dstr)
  recorderRepeat = list()
  while len(tLst) > 1:
    i = 1
    while i < len(tLst):
      if tLst[0] == tLst[i]:
        recorderRepeat.insert(0, i)
      i += 1
    if recorderRepeat:
      for i in recorderRepeat:
        tLst.pop(i)
      recorderRepeat.clear()
      tLst.pop(0)
    else:
      return tLst[0]
  if len(tLst) == 1:
    return tLst[0]
  else:
    return None

# 回文判断
def pld(dstr):
  if len(dstr) % 2 == 1:
    return False
  for i in range(int(len(dstr)/2)):
    if dstr[i] != dstr[-1-i]:
      return False
  return True

# 合并两个有序数组
def mergeLSt(lst1, lst2):
  bigLst = list()
  while lst1 and lst2:
    bigLst.append(lst1.pop(0)) if lst1[0] < lst2[0] else bigLst.append(lst2.pop(0))
  bigLst.extend(lst1 or lst2)
  return bigLst

# 数组中两数之和为目标值
def twosum(lst, t):
  for i in range(len(lst)):
    other = t - lst[i]
    for j in range(len(lst)-1, i, -1):
      if lst[j] == other:
        return (i, j)

# 最长公共子串
def maxSubStr(s1, s2):
  multLst = list()
  maxLen = 0
  maxLenS1Inx = 0
  for i in range(len(s1)):
    multLst.append(list())
    for j in range(len(s2)):
      if s1[i] == s2[j]:
        if i == 0 or j == 0:
          multLst[i].append(1)
        else:
          multLst[i].append(multLst[i-1][j-1] + 1)
      else:
        multLst[i].append(0)
    if max(multLst[i]) > maxLen:
      maxLen = max(multLst[i])
      maxLenS1Inx = i
  return maxLen, s1[i-maxLenS1Inx:maxLenS1Inx+1]

# 冒泡
def bubsort(lst):
  if len(lst) <= 1:
    return lst
  for i in range(len(lst),1,-1):
    for j in range(i-1):
      if lst[j] > lst[j+1]:
        lst[j], lst[j+1] = lst[j+1], lst[j]
  return lst

# 选择
def selesort(lst):
  for i in range(len(lst)-1):
    tmp = i
    for j in range(i+1, len(lst)):
      if lst[j] < lst[tmp]:
        tmp = j
    lst[i],lst[tmp] = lst[tmp],lst[i]
  return lst

# 插入
def insertsort(lst):
  for i in range(1, len(lst)-1):
    for j in range(i+1,0,-1):
      if lst[j] < lst[j-1]:
        lst[j], lst[j-1] = lst[j-1], lst[j]
      else:
        break
  return lst

# shell
def shellsort(lst):
  gap = len(lst) // 2
  while gap > 0:
    for i in range(gap,len(lst)):
      tmp = i
      cur = lst[i]
      # gap变小后有分组比较, 这里直接一次完成各组对比(tmp-gap>0;tmp=tmp-gap)
      while tmp-gap >= 0 and cur < lst[tmp-gap]:
        lst[tmp] = lst[tmp-gap]
        tmp = tmp - gap
      lst[tmp] = cur
    gap = gap // 2
  return lst

# mergesort
def mergesort(lst):
  if len(lst) < 2:
    return lst
  left = lst[0:len(lst)//2]
  right = lst[len(lst)//2::]
  return merge(mergesort(left), mergesort(right))

def merge(lst1, lst2):
  ret = list()
  while lst1 and lst2:
    if lst1[0] < lst2[0]:
      ret.append(lst1.pop(0))
    else:
      ret.append(lst2.pop(0))
  ret.extend(lst1)
  ret.extend(lst2)
  return ret

# 快排
def quicksork(lst, begin, end):
  if begin < end:
    tmp = lst[begin]
    i = begin
    j = end
    while i < j:
      while i < j and tmp < lst[j]:
        j = j-1
        lst[i] = lst[j]
      while i< j and tmp >= lst[j]:
        i = i+1
        lst[j] = lst[i]
    lst[i] = tmp
    quicksork(lst, begin, i-1)
    quicksork(lst,i+1,end)
  else:
    return None

if __name__ == '__main__':
  lst = [2,3,1,4,6,5,7]
  quicksork(lst, 0, 6)
  print(lst)
